package leetcode.t5Stack;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 42. 接雨水
 * hard
 *
 * @author K
 * @date 2024/1/19 16:18
 */
public class T42_Trap {

    public static int trap(int[] height) {
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        int current = 0;
        while (current < height.length) {
            //如果栈不空并且当前指向的高度大于栈顶高度就一直循环
            while (!stack.empty() && height[current] > height[stack.peek()]) {
                //出栈墙高度
                int popH = height[stack.peek()];
                //出栈，后面peek时取得更前面一个墙高度
                stack.pop();
                if (stack.empty()) {
                    // 栈空就出去，形成不了2堵钱
                    break;
                }
                //两堵墙之前的距离（宽）
                int distance = current - stack.peek() - 1;
                //两堵墙中矮墙高度
                int minH = Math.min(height[stack.peek()], height[current]);
                //矮墙与出栈墙的相对高度差（高），差值一定是非负数，因为入栈时是单调递减的
                int relativeH = minH - popH;
                sum = sum + distance * relativeH;
            }
            stack.push(current);
            current++;
        }
        return sum;
    }


    public static int trap2(int[] height) {
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        int current = 0;
        while (current < height.length) {
            while (!stack.isEmpty() && height[stack.peek()] < height[current]) {
                //取出要出栈的下标
                Integer hisIndex = stack.peek();
                int hisHigh = height[hisIndex];
                stack.pop(); //出栈
                if (stack.empty()) {
                    // 栈空就出去
                    break;
                }
                //两堵墙之前的距离。
                int distance = current - hisIndex - 1;
                int min = Math.min(height[stack.peek()], height[current]);
                sum = sum + distance * (min - hisHigh);

            }
            stack.add(current);
            current++;
        }
        return sum;
    }

    public static int trap1(int[] height) {
        int result = 0;
        Stack<Map<String, Integer>> stack = new Stack<>();
        Map<String, Integer> first = new HashMap<>();
        first.put("height", height[0]);
        first.put("index", 0);
//        stack.add(first);
        Map<String, Integer> left = first;
        for (int i = 1; i < height.length; i++) {
            int curH = height[i];
            if (i + 1 < height.length && curH > height[i + 1] && left.get("height") <= curH) {
                //计算盛水
                int sum = 0;
                while (!stack.empty()) {
                    Map<String, Integer> his = stack.pop();
                    Integer hisH = his.get("height");
                    if (stack.isEmpty()) {
                    } else {
                        sum += hisH;
                    }
                }
                int wide = i - left.get("index") - 1;
                int h = Math.min(left.get("height"), curH);
                result += wide * h - sum;

                stack.clear();
                left.put("height", curH);
                left.put("index", i);
            }
            if (i == height.length - 1) {
                if (!stack.isEmpty()) {
                    if (stack.peek().get("height")< curH) {
                        Map<String, Integer> map = new HashMap<>();
                        map.put("height", curH);
                        map.put("index", i);
                        stack.add(map);
                    }
                }
            } else {
                Map<String, Integer> map = new HashMap<>();
                map.put("height", curH);
                map.put("index", i);
                stack.add(map);
            }

        }

        if (!stack.isEmpty() && stack.size() >= 3) {
            Map<String, Integer> right = stack.pop();
            //计算盛水
            int sum = 0;
            while (!stack.empty()) {
                Map<String, Integer> his = stack.pop();
                Integer hisH = his.get("height");
                if (!stack.isEmpty()) {
                    sum += hisH;
                }
            }
            int wide = right.get("index") - left.get("index") - 1;
            int h = Math.min(left.get("height"), right.get("height"));
            result += wide * h - sum;
        }

        return result;
    }

    public static void main(String[] args) {
//        int result = trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
        int result1 = trap1(new int[]{4, 2, 0, 3, 2, 5});
        int result = trap(new int[]{4, 2, 0, 3, 2, 5});
        System.out.println();
    }
}
